#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 获取数组中最大数的位数
int getMaxDigits(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    int digits = 0;
    while (max != 0) {
        digits++;
        max /= 10;
    }
    return digits;
}

// 基数排序主函数
void radixSort(int arr[], int n) {
    // 获取最大位数
    int maxDigits = getMaxDigits(arr, n);
    
    // 创建临时数组
    int *output = (int *)malloc(n * sizeof(int));
    int count[10];
    
    // 从最低位开始排序
    for (int exp = 1; maxDigits > 0; exp *= 10, maxDigits--) {
        memset(count, 0, sizeof(count));
        
        // 统计每个数字出现的次数
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }
        
        // 计算累计次数
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        
        // 根据当前位数字排序
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        
        // 将排序结果复制回原数组
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }
    
    free(output);
}

// 测试函数
int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    radixSort(arr, n);
    
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}